/**
 * https://leetcode.cn/submissions/detail/577011005/
 * 788. 旋转数字
 * Medium, 黄伟杰 2024.1q0.30
 * 数位DP
 */
#include <bits/stdc++.h>
using namespace std;

int d[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
class Solution
{

public:
    int rotatedDigits(int n)
    {
        string s = to_string(n);
        int m = s.length(), dp[m][2];
        memset(dp, -1, sizeof(dp));
        // vector<vector<int>> memo(m, vector<int>(1 << 10, -1));
        auto dfs = [&](auto &&dfs, int i, int df, bool is_limit) -> int
        {
            if (i == m)
            {
                return df;
            }
            if (!is_limit && dp[i][df] != -1)
            {
                return dp[i][df];
            }
            int res = 0;
            int up = is_limit ? s[i] - '0' : 9;
            for (int j; j <= up; j++)
            {
                if (d[j] != -1)
                    res += dfs(dfs, i + 1, df || d[j], is_limit && j == up);
            }
            if (!is_limit)
                dp[i][df] = res;
            return res;
        };
        return dfs(dfs, 0, false, true);
    }
};